21. Merge Two Sorted Lists

題目描述：

給定兩個升序Linked List l1 和 l2，將它們合併為一個升序Linked List，並返回合併後的Linked List。

解題思路
這是我們第一個關於 Linked List 的題目，Linked List 在 LeetCode 中是非常常見的題目類型，讀者必須要能熟練掌握。回到這題的解法，相當直觀。首先，我們產生一個新的 Linked List，其頭節點稱為 dummy。接著，逐步比較兩個 Linked List 的當前節點，將較小的節點接入新 Linked List，並將指針向前移動，直到遍歷完其中一個 Linked List。之後，將未遍歷完的 Linked List 接到新 Linked List 的末尾。

var mergeTwoLists = function(l1, l2) {
    let dummy = new ListNode(0);
    let current = dummy;

    while (l1 !== null && l2 !== null) {
        if (l1.val < l2.val) {
            current.next = l1;
            l1 = l1.next;
        } else {
            current.next = l2;
            l2 = l2.next;
        }
        current = current.next;
    }

    if (l1 !== null) {
        current.next = l1;
    } else {
        current.next = l2;
    }

    return dummy.next;
};

時間複雜度：O(n + m)，其中 n 和 m 分別是 Linked List l1 和 l2 的長度。我們需要遍歷兩個 Linked List 中的每個節點。
空間複雜度：O(1)，我們只使用了常數空間來存儲指針和臨時變量，沒有使用額外的存儲空間。

總結
這道題目可以歸類為「dummy head」。回顧解題過程，當新 Linked List 加完所有的節點後，需要返回其頭節點，而這時我們一開始產生的 dummy 節點就起到了關鍵作用，因為 dummy.next 就是新 Linked List 的頭節點，也是最終需要返回的節點。這個技巧在後續解決 Linked List 題目時會反覆用到，建議讀者要熟悉並掌握。